package protect.week02;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/8 22:05
 * @package protect.week02
 * @description 14. 最长公共前缀
 * <p>
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * <p>
 * 如果不存在公共前缀，返回空字符串 ""。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * 示例 2：
 * <p>
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Ch04_LongestCommonPrefix {
    public String longestCommonPrefix(String[] strs) {

      /*
      分析：
         从后往前，逐步判断字符，如果不相同，则截取字符串，再进行判断
            1. 以字符串数组中的第一个元素作为参照元素
            2. 用参照字符串去对比其他字符串
            3. 如果不相同，则将第一个元素的长度从后缩短
            4. 返回参照字符串即可
       */
        if (strs.length == 0|| strs == null) {
            return "";
        }
        int k = strs[0].length();

        // 遍历字符串数组
        for (int i = 1; i < strs.length; i++) {
            // 判读 strs[i] 中是否存在子字符串 strs[0]，如果有则返回0，如果没有则返回 -1
            while (strs[i].indexOf(strs[0]) != 0){
                // 去掉字符串的最后一位
                //TODO 需要改进，每次减去1位，会导致重复判断
                strs[0] = strs[0].substring(0,strs[0].length()-1);
                // 当全部都不符合要求，则截取都没有了，返回空字符串即可
                if (strs[0].isEmpty()){
                    return "";
                }
            }
        }
        return strs[0];
    }

    public static void main(String[] args) {
        System.out.println(new Ch04_LongestCommonPrefix().longestCommonPrefix(new String[]{"122", "12"}));
    }
}
